/**
 * 
 */
package zhoujian.oj.leetcode;

import org.junit.Test;

/*
 * Given a string S, find the longest palindromic substring in S. 
 * You may assume that the maximum length of S is 1000, 
 * and there exists one unique longest palindromic substring.
 * 
 * Example:
 * 	input : babcbabcbaccba 
 * 	output : abcbabcba
 */

/**
 * @author hyper
 * @email zjkermit@gmail.com
 * @date Dec 12, 2013
 * @version 1.0
 * @description 
 */
public class LongestPalindromicSubstring {
	
	/*
	 * ========================================================================
	 * Simple algorithm
	 * The time complexity is O(n^2)
	 * The space complexity is O(1)
	 * ========================================================================
	 */
	public String simpleAlgorithm(String s) {
		if (s == null) {
			throw new IllegalArgumentException("input string can not be null!");
		}
		
		if (s.length() <= 1) {
			return s;
		}
		
		String longest = s.substring(0, 1);
		for (int i = 0; i < s.length(); i++) {
			// get longest palindrome with center of i
			String tmp = helper(s, i, i);
			if (tmp.length() > longest.length())
				longest = tmp;
			
			// get longest palindrome with center of i, i + 1
			tmp = helper(s, i, i + 1);
			if (tmp.length() > longest.length())
				longest = tmp;
		}
		
		return longest;
	}
	
	@Test
	public void testSimpleAlgorithm() {
		assert simpleAlgorithm("").equals("");
		assert simpleAlgorithm("a").equals("a");
		assert simpleAlgorithm("ab").equals("a");
		assert simpleAlgorithm("babcbabcbaccba").equals("abcbabcba");
		assert simpleAlgorithm("abacdfgdcaba").equals("aba");
	}
	
	// Given a center, either one letter or two letter,
	// Find longest palindrome
	public String helper(String s, int begin, int end) {
		while (begin >= 0 && end <= s.length() - 1 && s.charAt(begin) == s.charAt(end)) {
			begin--;
			end++;
		}
		return s.substring(begin + 1, end);
	}
	
	/*
	 * ========================================================================
	 * Using dynamic programming to solve the problem
	 * The time complexity is O(n^2)
	 * The space complexity is O(n^2)
	 * 
	 * table[i][i] == 1;
	 * table[i][i+1] == 1 => s.charAt(i) == s.charAt(i+1)
	 * table[i][j] == 1 => s.charAt(i) == s.charAt(j) && table[i+1][j-1] == 1
	 * ========================================================================
	 */
	public String dpSolution(String s) {
		if (null == s || s.isEmpty())
            return s;
            
        int len = s.length();
        boolean[][] dp = new boolean[len][len];
        for (int i = 0; i < len; ++i)
            dp[i][i] = true;
        int max = 1;
        String res = s.substring(0, 1);
        for (int i = 0; i < len - 1; ++i) {
            if (s.charAt(i) == s.charAt(i + 1)) {
                dp[i][i + 1] = true;
                if (max < 2) {
                    max = 2;
                    res = s.substring(i, i + 2);
                }
            }
        }
        
        for (int gap = 2; gap < len; ++gap) {
            for (int i = 0; i + gap < len; ++i) {
                if (s.charAt(i) == s.charAt(i + gap)) {
                    dp[i][i + gap] = dp[i + 1][i + gap - 1];
                    if (dp[i][i + gap] && gap + 1 > max) {
                        max = gap + 1;
                        res = s.substring(i, i + gap + 1);
                    }
                }
            }
        }
        
        return res;
	}
	
	public void printTable(int[][] x) {
		for (int[] y : x) {
			for (int z : y)
				System.out.print(z + " ");
			System.out.println();
		}
		System.out.println("------");
	}
	
	@Test
	public void testDpSolution() {
		assert dpSolution("").equals("");
		assert dpSolution("a").equals("a");
		assert dpSolution("ab").equals("a");
		assert dpSolution("babcbabcbaccba").equals("abcbabcba");
		assert dpSolution("abacdfgdcaba").equals("aba");
	}
	
	/*
	 * ========================================================================
	 * Using kmp algorithm to solve the problem, concretely using the longest
	 * common substring algorithm
	 * The time complexity is O(n^2)
	 * 
	 * method:
	 * 	reverse the input string, reStr
	 * 	enumerate every suffix of reStr, suf, we can pruning in the process
	 * 	compute the max matching length of the prefix of suf and input string
	 * ========================================================================
	 */
	public String kmpSolution(String str) {
		String reStr = new StringBuilder(str).reverse().toString();
		
		int maxLen = 0;
		String maxStr = "";
		for (int i = 0; i < reStr.length(); i++) {
			String suffix = str.substring(i);
			if (suffix.length() < maxLen) {
				break;
			}
			int len = compute(reStr, suffix);
			String temp = suffix.substring(0, len);
			if (len > maxLen && isPalindromic(temp)) {
				maxLen = len;
				maxStr = temp;
			}
		}
		
		return maxStr;
	}
	
	@Test
	public void testKmpSolution() {
		assert kmpSolution("").equals("");
		assert kmpSolution("a").equals("a");
		assert kmpSolution("ab").equals("a");
		assert kmpSolution("babcbabcbaccba").equals("abcbabcba");
		assert kmpSolution("abacdfgdcaba").equals("aba");
	}// equals C - (i - C), find the mirror of i, 
	
	// judge input string is palindromic or not
	private boolean isPalindromic(String str) {
		int length = str.length();
		
		if (length == 1) {
			return true;
		}
		
		int mid = (length - 1) / 2;
		int i = 0;
		int j = 0;
		
		if (length % 2 == 0) {
			i = mid;
			j = mid + 1;
		} else {
			i = mid - 1;
			j = mid + 1;
		}
		
		while (i >= 0) {
			if (str.charAt(i) != str.charAt(j)) {
				return false;
			}
			i--;
			j++;
		}
		
		return true;
	}
	
	@Test
	public void testIsPalindromic() {
		assert isPalindromic("abcbabcba");
	}
	
	// compute jump array
	private int[] getNext(String s) {
		int[] next = new int[s.length()];
		next[0] = -1;
	
		int i = 1;
		int pos;
		while (i < s.length()) {
			pos = next[i - 1];
			while (pos >= 0 && s.charAt(pos) != s.charAt(i - 1)) {
				pos = next[pos];
			}
			
			if (pos >= 0 && s.charAt(pos) == s.charAt(i - 1)) {
				next[i] = pos + 1;
			} else {
				next[i] = 0;
			}
			i++;
		}
		
		return next;
	}
	
	@Test
	public void testGetNext() {
		System.out.println("testGetNext");
		int[] next = getNext("abcabcda");
		for (int i : next) {
			System.out.print(i + " ");
		}
		System.out.println();
	}
	
	// core function, compute the longest prefix
	private int compute(String str, String pattern) {
		int maxLen = 0;
		int[] next = getNext(pattern);
		
		int i = 0;
		int j = 0;
		while (i < str.length()) {
			if (j == -1 || str.charAt(i) == pattern.charAt(j)) {
				i++;
				j++;
			} else {
				j = next[j];
			}
			
			if (j > maxLen) {
				maxLen = j;
			} 
			
			if (j == pattern.length()) {
				return maxLen;
			}
		}
		
		return maxLen;
	}
	
	@Test
	public void testCompute() {
		System.out.println("testCompute");
		System.out.println(compute("abcddca", "cddcba"));
	}
	
	/*
	 * ========================================================================
	 * Using Manacher's Algorithm to solve the problem
	 * The time complexity is O(n)
	 * 
	 * Method:
	 * 	Transform S into T.
	 * 	For example, S = "abba", T = "^#a#b#b#a#$".
	 * 	^ and $ are sentinels appended to each end to avoid bounds checking
	 * ========================================================================
	 */
	public String maSolution(String str) {
		if (str.length() == 0 || str.length() == 1) {
			return str;
		}
		
		String T = preProcess(str);
		int n = T.length();
		int[] P = new int[n];
		int C = 1;
		int R = 1;
		
		for (int i = 1; i < n - 1; i++) {
			// equals C - (i - C), find the mirror of i, C is center of im and i
			int im = 2 * C - i; 
			
			P[i] = (R > i) ? Math.min(R - i, P[im]) : 0;
			
			// Attempt to expand palindrome centered at i
			while (T.charAt(i + P[i] + 1) == T.charAt(i - P[i] - 1)) {
				P[i]++;
			}
			
			// If palindrome centered at i expand past R,
			// adjust center based on expanded palindrome.
			if (i + P[i] > R) {
				C = i;
				R = i + P[i];
			}
		}
		
		// Find the maximum element in P
		int maxLen = 0;
		int centerIndex = 0;
		for (int i = 1; i < n - 1; i++) {
			if (P[i] > maxLen) {
				maxLen = P[i];
				centerIndex = i;
			}
		}
		
		return str.substring((centerIndex - 1 - maxLen) / 2, (centerIndex - 1 - maxLen) / 2 + maxLen);
	}
	
	@Test
	public void testMaSolution() {
		assert maSolution("").equals("");
		assert maSolution("a").equals("a");
		assert maSolution("ab").equals("a");
		assert maSolution("babcbabcbaccba").equals("abcbabcba");
		assert maSolution("abacdfgdcaba").equals("aba");
	}
	
	// transform function
	private String preProcess(String str) {
		int n = str.length();
		if (n == 0) {
			return "^$";
		}
		
		StringBuilder sb = new StringBuilder();
		sb.append('^');
		for (int i = 0; i < n; i++) {
			sb.append('#');
			sb.append(str.charAt(i));
		}
		sb.append('#');
		sb.append('$');
		
		return sb.toString();
	}

	@Test
	public void testPreProcess() {
		String str = "abasdfasfasf";
		System.out.println(preProcess(str));
	} 
}
